package dag

import (
	"github.com/pkg/errors"
)

// Node DAG节点定义
type Node struct {
	ID        string                 `json:"id"` // 节点ID
	FieldName string                 `json:"fieldName"`
	TableName string                 `json:"tableName"`
	Metadata  map[string]interface{} `json:"metadata"`
}

// Edge DAG边定义
type Edge struct {
	SourceID string                 `json:"source_id"`
	TargetID string                 `json:"target_id"`
	Metadata map[string]interface{} `json:"metadata"`
}

// DAG 有向无环图结构
type DAG struct {
	Nodes   map[string]*Node   `json:"nodes"`
	Edges   map[string][]*Edge `json:"edges"`
	InEdges map[string][]*Edge `json:"in_edges"`
}

// NewDAG 创建新的DAG实例
func NewDAG() *DAG {
	return &DAG{
		Nodes:   make(map[string]*Node),
		Edges:   make(map[string][]*Edge),
		InEdges: make(map[string][]*Edge),
	}
}

// AddNode 添加节点到DAG
func (d *DAG) AddNode(node *Node) error {

	if _, exists := d.Nodes[node.ID]; exists {
		return errors.Errorf("DAG001: 节点已存在: %s", node.ID)
	}
	d.Nodes[node.ID] = node
	return nil
}

// AddEdge 添加边到DAG
func (d *DAG) AddEdge(edge *Edge) error {
	// 检查源节点和目标节点是否存在
	if _, exists := d.Nodes[edge.SourceID]; !exists {
		return errors.Errorf("源节点不存在: source_id=%s", edge.SourceID)
	}

	if _, exists := d.Nodes[edge.TargetID]; !exists {
		return errors.Errorf("目标节点不存在: target_id=%s", edge.TargetID)
	}

	// 检查是否会形成环
	if d.HasCycleAfterAdd(edge) {
		return errors.Errorf("添加边会形成环: source_id=%s, target_id=%s", edge.SourceID, edge.TargetID)
	}

	// 添加边
	d.Edges[edge.SourceID] = append(d.Edges[edge.SourceID], edge)
	d.InEdges[edge.TargetID] = append(d.InEdges[edge.TargetID], edge)
	return nil
}

// GetDependents 获取节点的所有依赖节点
func (d *DAG) GetDependents(nodeID string) []*Node {
	var result []*Node
	for _, edge := range d.Edges[nodeID] {
		if node, exists := d.Nodes[edge.TargetID]; exists {
			result = append(result, node)
		}
	}
	return result
}

// GetDependencies 获取节点的所有前置依赖节点
func (d *DAG) GetDependencies(nodeID string) []*Node {
	var result []*Node
	for _, edge := range d.InEdges[nodeID] {
		if node, exists := d.Nodes[edge.SourceID]; exists {
			result = append(result, node)
		}
	}
	return result
}

// HasCycle 检查DAG是否有环
func (d *DAG) HasCycle() bool {
	visited := make(map[string]bool)
	recStack := make(map[string]bool)

	for nodeID := range d.Nodes {
		if !visited[nodeID] && d.hasCycleDFS(nodeID, visited, recStack) {
			return true
		}
	}
	return false
}

// hasCycleDFS 深度优先搜索检查环
func (d *DAG) hasCycleDFS(nodeID string, visited, recStack map[string]bool) bool {
	if !visited[nodeID] {
		visited[nodeID] = true
		recStack[nodeID] = true

		for _, edge := range d.Edges[nodeID] {
			neighborID := edge.TargetID
			if !visited[neighborID] && d.hasCycleDFS(neighborID, visited, recStack) {
				return true
			} else if recStack[neighborID] {
				return true
			}
		}
	}
	recStack[nodeID] = false
	return false
}

// HasCycleAfterAdd 检查添加边后是否会形成环
func (d *DAG) HasCycleAfterAdd(edge *Edge) bool {
	// 临时添加边
	d.Edges[edge.SourceID] = append(d.Edges[edge.SourceID], edge)
	d.InEdges[edge.TargetID] = append(d.InEdges[edge.TargetID], edge)

	// 检查环
	hasCycle := d.HasCycle()

	// 移除临时添加的边 - 通过比较边的源和目标ID而不是指针
	edges := d.Edges[edge.SourceID]
	for i, e := range edges {
		if e.SourceID == edge.SourceID && e.TargetID == edge.TargetID {
			edges = append(edges[:i], edges[i+1:]...)
			break
		}
	}
	d.Edges[edge.SourceID] = edges

	inEdges := d.InEdges[edge.TargetID]
	for i, e := range inEdges {
		if e.SourceID == edge.SourceID && e.TargetID == edge.TargetID {
			inEdges = append(inEdges[:i], inEdges[i+1:]...)
			break
		}
	}
	d.InEdges[edge.TargetID] = inEdges

	return hasCycle
}

// TopologicalSort 执行拓扑排序
func (d *DAG) TopologicalSort() ([]*Node, error) {
	if d.HasCycle() {
		return nil, errors.Errorf("DAG005: DAG中存在环，无法进行拓扑排序")
	}

	visited := make(map[string]bool)
	result := []*Node{}

	for nodeID := range d.Nodes {
		if !visited[nodeID] {
			d.topologicalSortDFS(nodeID, visited, &result)
		}
	}

	// 反转结果以获得正确的拓扑顺序
	for i, j := 0, len(result)-1; i < j; i, j = i+1, j-1 {
		result[i], result[j] = result[j], result[i]
	}

	return result, nil
}

// topologicalSortDFS 拓扑排序的深度优先搜索实现
func (d *DAG) topologicalSortDFS(nodeID string, visited map[string]bool, result *[]*Node) {
	visited[nodeID] = true

	for _, edge := range d.Edges[nodeID] {
		neighborID := edge.TargetID
		if !visited[neighborID] {
			d.topologicalSortDFS(neighborID, visited, result)
		}
	}

	*result = append(*result, d.Nodes[nodeID])
}
